1. Field of the Invention
The present invention relates generally to memory circuits, and more particularly to built-in self test (BIST) circuitry for content addressable memory (CAM) circuits.
2. Description of the Related Art
Modern computer systems and computer networks utilize memory devices for storing data and providing fast access to the data stored therein. A content addressable memory (CAM) is a special type of memory device often used for performing fast destination searches for data stored in the CAM. For example, Internet routers often include a CAM for searching the address of specified data. Thus, the use of CAMs allows routers to perform address searches to facilitate more efficient communication between computer systems over computer networks. Besides routers, CAMs are also utilized in other areas where fast-searches are required such as databases, network adapters, image processing, voice recognition applications, etc.
Conventional CAMs typically include a two-dimensional row and column content addressable memory core array of cells. In such an array, each row typically stores an address, pointer, or bit pattern entry. In a read/write configuration, a CAM may perform “read” and “write” operations at specific addresses as is done in conventional random access memories (RAMs). In another configuration, CAMs unlike RAMs, can perform data “search” operations that simultaneously compare a bit pattern of data against an entire list (i.e., column) of prestored entries (i.e., rows).
As with most memory devices, the conventional CAMs may fail to operate properly due to any number of faults. For example, bit cells of the CAM array may become stuck at some value. Another type of fault occurs when bit cells become electrically coupled during write operations. In such cases, when a specific value is written to one bit cell, the other bit cell in the same row or a different row acquires the same value. Another type of fault is a transition fault, which prevents a bit cell from transitioning from one state into another state. Yet another example is when an address decoding fault occurs, thus causing a wrong cell or cells to be addressed, thereby resulting in the access of data in the wrong location.
Still another type of fault occurs when electrical shorts or other defects cause circuit or memory elements to be stuck-at some value, thereby preventing proper operation of the CAM. Such faults may occur in a CAM itself or its peripheral circuitry. Another fault occurs when CAM circuits operate at a slower speed than expected due to variations in such factors as IC fabrication process, temperature, or voltage. As can be appreciated, such dynamic faults cause undesired delays that can degrade performance of CAM circuits.
To guard against such faults, one approach is to implement a built-in self-test (BIST) technique for detecting some of these types of faults. For example, U.S. Pat. No. 5,107,501 by Yervant Zorian, which is incorporated herein by reference, discloses a BIST technique for testing the data bits in a conventional binary CAM using write and read-match operations. While such method detects faults such as electrical short and open faults and stuck-at faults, it is not well suited for detecting faults in ternary CAMs. Specifically, the bit cells in ternary CAMs are characterized not only by binary states of “0” and “1,” but also by a “don't care” state, which denotes that the state of the associated bit cell is not relevant to a particular CAM search. Consequently, not all functional aspects of a ternary CAM can be tested using the teachings of Zorian.
Also, Zorian can only perform writes to set up searches when search operations are not being performed. Consequently, there will be cases in which BIST searching cannot be performed for several cycles until write operations are complete. This, of course, slows down BIST testing and does not allow the BIST testing to be at the functional speed. Furthermore, the BIST technique described by Zorian tests the CAM rows simultaneously. This technique triggers matches in all rows of the CAM and results in very high power consumption. In essence, the Zorian design is impractical for today's larger CAM implementations. Practical CAM devices with large storage capacities are designed to be used only in a manner that does not cause matches in more than some limited number of rows simultaneously.
In view of the foregoing, what is needed is a method for BIST testing of CAM circuitry and associated BIST testing circuitry.